package interview.tablesum;

import java.util.HashSet;
import java.util.Iterator;

public class TableSum {
	public boolean run(int sum, int[][] table, int m, int n) {
		HashSet<Integer> setI = new HashSet<Integer>();
		HashSet<Integer> setJ = new HashSet<Integer>();
		HashSet<String> setIJ = new HashSet<String>();
		
		dumpTable(table, m, n);
		return tableSum(sum, table, m, n, Math.min(m, n), setI, setJ, setIJ);
	}

	private void dumpTable(int[][] table, int m, int n) {
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				System.out.print("\t" + table[i][j]);
			}
			System.out.println();
		}
	}

	@SuppressWarnings("unchecked")
	private boolean tableSum(int sum, int[][] table, int m, int n, int min,
			HashSet<Integer> setI, HashSet<Integer> setJ, HashSet<String> setIJ) {
		if(sum == 0 && setIJ.size() != 0) {
			printResult(setIJ);
			return true;
		}
		
		if((setI.size() == min || setJ.size() == min) && sum != 0) {
			return false;
		}
		
		HashSet<Integer> iclone;
		HashSet<Integer> jclone;
		HashSet<String> ijclone;
		
		for(int i = 0; i < m; i++) {
			if(setI.contains(i)) {
				continue;
			}
			iclone = (HashSet<Integer>)setI.clone();
			iclone.add(i);
			jclone = (HashSet<Integer>)setJ.clone();
			ijclone = (HashSet<String>)setIJ.clone();
			if(tableSum(sum, table, m, n, min, iclone, jclone, ijclone)) {
				return true;
			}
			for(int j = 0; j < n; j++) {
				if(setJ.contains(j)) {
					continue;
				}
				iclone = (HashSet<Integer>)setI.clone();
				jclone = (HashSet<Integer>)setJ.clone();
				jclone.add(j);
				ijclone = (HashSet<String>)setIJ.clone();
				if(tableSum(sum, table, m, n, min, iclone, jclone, ijclone)) {
					return true;
				}
				if(table[i][j] != 0) {
					iclone = (HashSet<Integer>)setI.clone();
					iclone.add(i);
					jclone = (HashSet<Integer>)setJ.clone();
					jclone.add(j);
					ijclone = (HashSet<String>)setIJ.clone();
					ijclone.add("a[" + i + "] <==> b[" + j + "]");
					if(tableSum(sum - table[i][j], table, m, n, min, iclone, jclone, ijclone)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private void printResult(HashSet<String> setIJ) {
		Iterator<String> ijit = setIJ.iterator();
		while(ijit.hasNext()) {
			System.out.println(ijit.next());
		}
	}
}
